package LLParser;

import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class LL1ParserGenerator {
	
	private String fileName;
	private Set<String> tokenSet;
	private ArrayList<Rule> ruleList;
	private ArrayList<String> ruleNameList;
	private HashMap<String, String> firstMap;
	private ParseTable pTable;
	private String start;
	
	public LL1ParserGenerator(String fileName)
	{
		this.fileName = fileName;
		tokenSet = new HashSet<String>();
		ruleList = new ArrayList<Rule>();
		ruleNameList = new ArrayList<String>();
		firstMap = new HashMap<String, String>();
		pTable = new ParseTable();
		start = null;
	}
	
	public void parseGrammar()
	{
		Scanner scan;
		String line;
		ArrayList<Rule> toFactorList = new ArrayList<Rule>();
		ArrayList<Rule> toFactorSet = new ArrayList<Rule>();
		
		try {
			scan = new Scanner(new File(fileName));
			
			//Scan in the LL1 Grammar
			while(scan.hasNextLine())
			{
				line = scan.nextLine();
				
				if(line.contains("Tokens"))
				{
					//Skip empty lines
					while((line = scan.nextLine()).equals(""));
					
					parseTokens(line);
				}
				else if(line.contains("%% Start"))
				{
					//Skip empty space lines
					while((line = scan.nextLine()).equals(""));

					start = line;
				}
				else if(line.contains("%% Rules"))
				{
					while(scan.hasNextLine())
					{
						line = scan.nextLine();
						
						toFactorList.addAll(parseRule(line));
					}
				}
			}
			
			//factor the grammar
			for(int i = 0; i < toFactorList.size(); i++)
			{
				if(toFactorSet.size() == 0)
					toFactorSet.add(toFactorList.get(i));
				else if(toFactorSet.get(0).getRuleName().equals(toFactorList.get(i).getRuleName()))
				{
					toFactorSet.add(toFactorList.get(i));
				}
				else
				{
					ruleList.addAll(factor(toFactorSet));
					toFactorSet.clear();
					toFactorSet.add(toFactorList.get(i));
				}
			}
			
			if(!toFactorSet.isEmpty())
				ruleList.addAll(factor(toFactorSet));
			
			
			//Set Rule Numbers
			for(int i = 0; i < ruleList.size(); i++)
			{
				ruleList.get(i).setRuleNum(i);
			}
			
			setRuleNameList();
			
			//Add to Table
			for(Rule r : ruleList)
			{
				ruleToTable(r);
			}

		} catch(Exception e) {
			e.printStackTrace();
		}
	}

	public void parseTokens(String line)
	{
		String[] tokenList = line.split("[ ]+");
		
		for(String s : tokenList)
		{
			tokenSet.add(s);
		}		
	}
	
	/**
	 * Creates a Rule - The rule ArrayList is populated by each terminal and nonterminals are given 1 slot.
	 * 
	 * @param line
	 */
	private ArrayList<Rule> parseRule(String line)
	{
		ArrayList<Rule> list = new ArrayList<Rule>();
		
		if(line.equals(""))
			return list;
		
		String[] ruleLine = line.split(":|\\||->|::=");
		String ruleName = ruleLine[0].trim();
		
		for(int i = 1; i < ruleLine.length; i++)
		{
			ArrayList<String> ruleList = new ArrayList<String>();
			
			String[] rule = ruleLine[i].split(" ");
			
			for(int j = 0; j < rule.length; j++)
			{
				if(!rule[j].equals(""))
					ruleList.add(rule[j]);
			}
			
			list.add(new Rule(ruleName, ruleList));
		}
		
		return list;
	}
	
	private ArrayList<Rule> factor(ArrayList<Rule> list)
	{
		if(list.size() == 1)
			return list;
	
		boolean hit = false;
		String factor;
		String ruleName = list.get(0).getRuleName();
		ArrayList<Rule> newList = new ArrayList<Rule>();
		
		while(list.size() != 0)
		{
			hit = false;
			factor = list.get(0).getRule().get(0);
			
			for(int i = 1; i < list.size(); i++)
			{
				if(factor.equals(list.get(i).getRule().get(0)))
				{
					hit = true;
					list.get(i).getRule().remove(0);
					list.get(i).setRuleName(newRuleName(ruleName));
				}
			}
			
			if(hit)
			{
				//Generate new Rule
				ArrayList<String> newRule = new ArrayList<String>();
				newRule.add(factor);
				newRule.add(newRuleName(ruleName));
				
				//Add new rule to the return List
				newList.add(new Rule(list.get(0).getRuleName(), newRule));
				
				//Rename the factor rule
				list.get(0).getRule().remove(0);
				list.get(0).setRuleName(newRuleName(ruleName));
				
				//Rename the new rule name
				ruleName = newRuleName(ruleName);
			}
			else
			{
				//Add the top rule to the list
				newList.add(list.get(0));
				//Remove the rule from the list
				list.remove(0);
			}
		}

		return newList;
	}
	
	private void ruleToTable(Rule rule)
	{
		String terminal;
		Set<String> terminals = new HashSet<String>();
		
		if(rule.getRule().get(0).contains("<"))
		{
			terminals.addAll(getFirst(rule.getRule().get(0)));
		}
		else if(rule.getRule().get(0).equals("EPSILON"))
		{
			terminals.addAll(getFollow(rule.getRuleName()));
		}
		else
			terminals.add(rule.getRule().get(0));
		
		Iterator it = terminals.iterator();
		
		System.out.print(rule.getRuleName());
		
		while(it.hasNext())
		{
			terminal = (String) it.next();
			
			pTable.addTransition(rule.getRuleName(), terminal, rule.getRuleNum());
			
			System.out.print(" " + terminal);
		}
		
		System.out.println();
	}
	
	private Set<String> getFirst(String ruleName)
	{
		Set<String> terminals = new HashSet<String>();
		
		for(Rule r : ruleList)
		{
			if(r.getRuleName().equals(ruleName))
			{
				if(r.getRule().get(0).contains("<"))
				{
					terminals.addAll(getFirst(r.getRule().get(0)));
				}
				else if(!r.getRule().get(0).equals("EPSILON"))
				{
					terminals.add(r.getRule().get(0));
				}
			}
		}
		
		
		return terminals;
	}
	
	private Set<String> getFollow(String ruleName)
	{
		int index;
		Set<String> terminals = new HashSet<String>();
		
		for(Rule r : ruleList)
		{
			if((index = r.getRule().indexOf(ruleName)) != -1)
			{
				if(index == r.getRule().size() - 1)
				{
					if(!(r.getRuleName().equals(ruleName) && r.getRule().get(r.getRule().size() - 1).equals(ruleName)))
						terminals.addAll(getFollow(r.getRuleName()));
				}
				else
				{
					if(r.getRule().get(index + 1).charAt(0) == '<')
						terminals.addAll(getFirst(r.getRule().get(index + 1)));
					else
						terminals.add(r.getRule().get(index + 1));
				}
			}
		}
		
		return terminals;
	}
	
	private void setRuleNameList()
	{
		for(Rule r : ruleList)
		{
			if(!ruleNameList.contains(r.getRuleName()))
				ruleNameList.add(r.getRuleName());
		}
	}
	
	public String newRuleName(String ruleName)
	{
		return ruleName.substring(0, ruleName.length() - 1) + "'>";
	}
	
	public ArrayList<Rule> getRuleList()
	{
		return ruleList;
	}
	
	public ParseTable getParseTable()
	{
		return pTable;
	}
	
	public Set getTokenSet()
	{
		return tokenSet;
	}
	
	public String getStart()
	{
		return start;
	}
}
